//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int n = prices.size();
//        vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f3f));
//        auto g = f;
//        f[0][0] = -prices[0];
//        g[0][0] = 0;
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j < 3; j++)
//            {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//                g[i][j] = g[i - 1][j];
//                if (j >= 1)
//                {
//                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        auto ret = 0;
//        for (int i = 0; i < 3; i++)
//        {
//            ret = max(ret, g[n - 1][i]);
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        int n = prices.size();
//        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
//        auto g = f;
//        f[0][0] = -prices[0];
//        g[0][0] = 0;
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j < k + 1; j++)
//            {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//                g[i][j] = g[i - 1][j];
//                if (j >= 1)
//                {
//                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        auto ret = 0;
//        for (int i = 0; i <= k; i++)
//        {
//            ret = max(ret, g[n - 1][i]);
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    int maxSubArray(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        int ret = -INT_MAX;
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
//            ret = max(ret, dp[i]);
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int maxSubarraySumCircular(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        auto g = f;
//        int ret1 = INT_MIN, ret2 = INT_MAX;
//        int sum = 0;
//        for (auto e : nums) sum += e;
//        for (int i = 1; i <= n; i++)
//        {
//            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
//            ret1 = max(ret1, f[i]);
//        }
//        for (int i = 1; i <= n; i++)
//        {
//            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
//            ret2 = min(ret2, g[i]);
//        }
//        if (sum == ret2) return ret1;
//        return max(ret1, sum - ret2);
//    }
//};


//class Solution {
//public:
//    int maxProduct(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        auto g = f;
//        f[0] = g[0] = 1;
//        int ret = INT_MIN;
//        for (int i = 1; i <= n; i++)
//        {
//            f[i] = max(nums[i - 1], max(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));
//            ret = max(ret, f[i]);
//            g[i] = min(nums[i - 1], min(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int getMaxLen(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        auto g = f;
//        int ret = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            if (nums[i - 1] > 0)
//            {
//                f[i] = f[i - 1] + 1;
//                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//            }
//            if (nums[i - 1] < 0)
//            {
//                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//                g[i] = f[i - 1] + 1;
//            }
//            ret = max(ret, f[i]);
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n);
//        for (int i = 2; i < n; i++)
//        {
//            int a = nums[i - 2];
//            int b = nums[i - 1];
//            int c = nums[i];
//            dp[i] = c - b == b - a ? dp[i - 1] + 1 : 0;
//        }
//        auto ret = 0;
//        for (auto e : dp) ret += e;
//        return ret;
//    }
//};

